#include <iostream>
#include <vector>
using namespace std;

template <typename T, typename Compare = less<T>>
class BSTree
{
public:
    BSTree()
    {
        root_ = nullptr;
    }
    ~BSTree()
    {
    }
    // 非递归的插入操作
    void n_insert(const T &value)
    {
        if (root_ == nullptr)
        {
            root_ = new Node(value);
            return;
        }
        Node *parent = nullptr;
        Node *cur = root_;
        while (cur != nullptr)
        {
            parent = cur;
            if (!comp_(cur->value, value))
            {
                // 大于关系
                cur = cur->left_node;
            }
            else if (comp_(cur->value, value))
            {
                cur = cur->right_node;
            }
            else
            {
                return;
            }
        }
        if (comp_(value, parent->value))
        {
            parent->left_node = new Node(value);
        }
        else if (!comp_(value, parent->value))
        {
            parent->right_node = new Node(value);
        }
    }
    // 非递归删除操作
    void n_remove(const T &value)
    {
        if (root_ == nullptr)
        {
            return;
        }
        Node *father = nullptr;
        Node *cur = root_;
        while (cur != nullptr)
        {
            if (!comp_(cur->value, value))
            {
                // 大于关系
                father = cur;
                cur = cur->left_node;
            }
            else if (comp_(cur->value, value))
            {
                father = cur;
                cur = cur->right_node;
            }
            else
            {
                // 找到待删除节点
                break;
            }
        }

        if (cur == nullptr)
        {
            return;
        }

        // 先处理有两个孩子节点的。
        // 将有两个孩子节点的转换成有一个孩子节点的或者没有孩子节点的。
        if (cur->right_node != nullptr && cur->left_node != nullptr)
        {
            // 找cur的前驱节点
            Node *pre = cur->left_node;
            while (pre->right_node != nullptr)
            {
                father = pre;
                pre = pre->right_node;
            }
            cur->value = pre->value;
            cur = pre;
        }

        Node *child = cur->left_node;
        if (child == nullptr)
        {
            child = cur->right_node;
        }
        if (father == nullptr)
        {
            // 表示删除的是根节点。
            root_ = child;
        }
        else
        {
            if (father->left_node == cur)
            {
                father->left_node = child;
            }
            else if (father->right_node == cur)
            {
                father->right_node = child;
            }
        }

        delete cur; // 删除待删除结点
    }
    // 递归删除操作
    void remove(const T &value)
    {
        if (root_ == nullptr)
        {
            return;
        }
        root_ = remove(root_, value);
    }
    // 递归查询操作
    bool find(const T &value)
    {
        return find(root_, value);
    }
    // 递归插入
    void insert(const T &value)
    {
        root_ = insert(root_, value);
    }
    // 递归前序遍历操作
    void preOrder()
    {
        cout << "[递归]前序遍历";
        preOrder(root_);
        cout << endl;
    }
    // 递归中序遍历
    void inOrder()
    {
        cout << "[递归]中序遍历";
        inOrder(root_);
        cout << endl;
    }
    // 递归后序遍历
    void postOrder()
    {
        cout << "[递归]后序遍历";
        postOrder(root_);
        cout << endl;
    }
    // 递归层序遍历
    void level()
    {
        int hight = getLevel(root_);
        cout << "[递归]层序遍历";
        for (int i = 0; i < hight; i++)
        {
            level(root_, i);
        }
        cout << endl;
    }
    //查找区间内符合的元素[i,j]
    void findValues(vector<T>& vec,int first,int last)
    {
        findValues(root_,vec,first,last);
    }
    //判断一颗二叉树是否是BST
    bool isBSTree()
    {
        Node* pre = nullptr;
        return isBSTree(root_,pre);
    }
    //判断一棵树是否是当前树的子树
    bool isChild(BSTree<T,Compare>& childBst)
    {
        if(childBst.root_ == nullptr)
        {
            return true;
        }
        Node* cur = root_;
        while(cur != nullptr)
        {
            if(cur->value == childBst.root_->value)
            {
                break;
            }
            else if(comp_(cur->value,childBst.root_->value))
            {
                cur = cur->right_node;
            } else 
            {
                cur = cur->left_node;
            }
        }
        if(cur == nullptr)
        {
            return false;
        }

        return isChild(cur,childBst.root_);
    }
    //根据前序和中序遍历数组，构建二叉树
    void rebuild(int pre[],int i,int j,int in[],int m,int n)
    {
        root_ = _rebuild(pre,i,j,in,m,n);
    }
private:
    struct Node
    {
        Node(T value = T()) : value(value), left_node(nullptr), right_node(nullptr)
        {
        }
        T value;          // 节点域
        Node *left_node;  // 指向左孩子
        Node *right_node; // 指向右孩子
    };
    // 递归层序遍历
    void level(Node *node, int i)
    {
        if (node == nullptr)
        {
            return;
        }
        if (i == 0)
        {
            cout << node->value << " ";
            return;
        }
        level(node->left_node, i - 1);
        level(node->right_node, i - 1);
    }
    // 递归求二叉树的层数
    int getLevel(Node *node)
    {
        if (node == nullptr)
        {
            return 0;
        }
        int left = getLevel(node->left_node);
        int right = getLevel(node->right_node);
        return left > right ? left + 1 : right + 1;
    }
    // 递归前序遍历实现
    void preOrder(Node *node)
    {
        if (node == nullptr)
        {
            return;
        }
        cout << node->value << " ";
        preOrder(node->left_node);
        preOrder(node->right_node);
    }
    // 递归中序遍历实现
    void inOrder(Node *node)
    {
        if (node == nullptr)
        {
            return;
        }
        inOrder(node->left_node);
        std::cout << node->value << " ";
        inOrder(node->right_node);
    }
    // 递归后序遍历实现
    void postOrder(Node *node)
    {
        if (node == nullptr)
        {
            return;
        }
        postOrder(node->left_node);
        postOrder(node->right_node);
        std::cout << node->value << " ";
    }
    // 递归查询操作
    bool find(Node *node, const T &value)
    {
        if (node == nullptr)
        {
            return false;
        }
        if (comp_(value, node->value))
        {
            return find(node->left_node, value);
        }
        else if (comp_(node->value, value))
        {
            return find(node->right_node, value);
        }
        return true;
    }
    // 递归插入操作
    // 把当前节点在回溯的过程中返回给其父节点。
    Node *insert(Node *node, const T &value)
    {
        if (node == nullptr)
        {
            // 递归结束，找到插入value的位置，生成新节点并返回其节点地址
            return new Node(value);
        }
        if (node->value == value)
        {
            return node;
        }
        else if (comp_(node->value, value))
        {
            node->right_node = insert(node->right_node, value);
        }
        else
        {
            node->left_node = insert(node->left_node, value);
        }
        return node;
    }
    Node *remove(Node *node, const T &value)
    {
        // 将待删除节点的孩子传递给其父节点。
        // 如果有两个孩子那就将前驱节点放到待删除节点（覆盖），然后删除前驱节点。
        if (node == nullptr)
        {
            return nullptr;
        }
        if (node->value == value)
        {
            // 找到要删除的节点
            if (node->left_node != nullptr && node->right_node != nullptr)
            {
                // 如果有两个孩子那就将前驱节点放到待删除节点（覆盖），然后删除前驱节点。
                //  找node的前驱节点
                Node *pre = node->left_node;
                while (pre->right_node != nullptr)
                {
                    pre = pre->right_node;
                }
                node->value = pre->value;
                node->left_node = remove(node->left_node, value);
            }
            else if (node->left_node != nullptr)
            {
                Node *tmp = node->left_node;
                delete node;
                return tmp;
            }
            else if (node->right_node != nullptr)
            {
                Node* tmp = node->right_node;
                delete node;
                return tmp;
            }
        }
        else if (comp_(node->value, value))
        {
            node->right_node = remove(node->right_node, value);
        }
        else
        {
            node->left_node = remove(node->left_node, value);
        }
        return node;
    }
    //查找区间内元素
    void findValues(Node* node,vector<T>& vec,int first,int last)
    {
        //利用递归中序遍历
        if(node != nullptr)
        {
            if(node->value > first)
            {   
                //如果当前节点的值都比最小值还小了，就没有必要往左子树走了，左子树都比当前节点小，再遍历也没有意思了。
                findValues(node->left_node,vec,first,last);
            }
            
            //v
            if(node->value >= first && node->value <= last)
            {
                vec.push_back(node->value);
            }
            if(node->value < last)
            {
                //如果当前节点的值都比最大值大了，就没有必要往右子树走了。
                findValues(node->right_node,vec,first,last);
            } 
        }
    }
    bool isBSTree(Node* node,Node* &pre)
    {
        //利用BST的中序遍历一定是一个升序的数组。
        if(node == nullptr)
        {
            return true;
        }
        if(!isBSTree(node->left_node,pre))
        {
            //L
            //如果左子树已经不是BST了那就不用往下走了
            return false;

        }
        //v
        if(pre != nullptr)
        {
            if(comp_(node->value,pre->value))
            {
                return false;
            }
        }
       
        pre = node;
        return isBSTree(node->right_node,pre);
    }
    bool isChild(Node* father,Node* son)
    {
        if(father == nullptr && son == nullptr)
        {
            return true;
        }

        if(son == nullptr)
        {
            return true;
        }
        if(father == nullptr)
        {
            return false;
        }
        if(father->value != son->value)
        {
            return false;
        }

        return isChild(father->left_node,son->left_node) && isChild(father->right_node,son->right_node);
    }
    //根据前序和中序遍历数组，构建二叉树,递归实现
    Node* _rebuild(int pre[],int beginPre,int endPre,int in[],int beginIn,int endIn)
    {
        if(beginPre > endPre || beginIn > endIn)
        {
            return nullptr;
        }

        int rootValue = pre[beginPre];
        //创建当前子树的根节点
        Node* rootNode = new Node(root);

        //查找根节点在中序遍历中的位置
        int rootIndex = beginIn;
        while(rootIndex != endIn && in[rootIndex] != rootValue)
        {
            rootIndex++;
        }
        //计算左子树长度
        int leftLen = rootIndex - beginIn;

        node->left_node = _rebuild(pre,beginPre + 1,beginPre +leftLen,in,beginIn,rootIndex - 1);
        node->right_node = _rebuild(pre,beginPre + leftLen + 1,endPre,in,rootIndex + 1,endIn);
        
        return node;
    }
    Node *root_;   // 指向bst树的根节点
    Compare comp_; // 指定一个函数对象
};
void test()//测试重建二叉树
{
    BSTree<int> bst;
    int pre[] = {58,24, 0 ,5, 34 ,41 ,67 ,62 ,64 ,69, 78};
    int in[] = {0, 5 ,24 ,34 ,41 ,58 ,62, 64, 67, 69 ,78};
    bst.rebuild(pre,0,10,in,0,10);
    bst.preOrder();
    bst.inOrder();
    bst.level();
}
int main()
{
    test();
    // int arr[] = {58, 24, 67, 0, 34, 62, 69, 5, 41, 64, 78};
    // BSTree<int> bst;
    // for (auto i : arr)
    // {
    //     bst.insert(i);
    // }
    // bst.preOrder();
    // bst.inOrder();
    // bst.postOrder();
    // bst.level();
    // std::cout << std::boolalpha;
    // std::cout << bst.find(0) << std::endl;
    // std::cout << std::noboolalpha;
    // bst.remove(0);
    // bst.level();
    // vector<int> vec;
    // bst.findValues(vec,10,60);
    // for(auto i : vec)
    // {
    //     std::cout << i << " ";
    // }
    // cout << endl;

    // std::cout << std::boolalpha;
    // std::cout << bst.isBSTree() << std::endl;
    // std::cout << std::noboolalpha;
    // int arr2[] = { 67, 62};
    // BSTree<int> bst2;
    // for (auto i : arr2)
    // {
    //     bst2.insert(i);
    // }
    // bst2.level();
    // std::cout << std::boolalpha;
    // std::cout << bst.isChild(bst2) << std::endl;
    // std::cout << std::noboolalpha;

}